1. Field of the Invention
The present invention relates to the design of digital circuits. More specifically, the present invention relates to a method and an apparatus for controlling state information within a circuit.
2. Related Art
Finite state machines are familiar to every designer of computer equipment. They are easy to describe and generally easy to implement. Such a machine can be in any one of a number of xe2x80x9cstatesxe2x80x9d. Most implementations use a set of xe2x80x9cstate flip-flopsxe2x80x9d to hold the present state of the finite state machine.
For each state there are a set of conditions that will cause the finite state machine to change from that state to some other state. The conditions examined in each state may be unique to that state or shared with other states. The state to which the device changes depends on the state it is in, the conditions examined in that state, and which conditions are TRUE.
For example, a simple up-down counter is a finite state machine. Its states are the finite number of count values that it can hold. The conditions examined in each state are xe2x80x9ccount upxe2x80x9d and xe2x80x9ccount downxe2x80x9d. The up-down counter advances from its present state to the next higher count value when it gets the xe2x80x9ccount upxe2x80x9d condition and advances to the next lower count value when it finds the xe2x80x9ccount downxe2x80x9d condition. Depending on the design it may have a highest state in which it can only count down or a lowest state in which it can only count up or both.
Finite state machines typically use externally-clocked flip-flops to hold their state. Logic elements examine the conditions pertinent to the present state, and upon the arrival of each external clock pulse, set or clear selected clocked flip-flops to establish the next state. The design of such externally-clocked finite state machines is relatively easy, because all flip-flops change, if at all, only in response to the same external clock signal. Thus, for example, it is acceptable to change the state of several flip-flops at once, for example as happens in a binary counter when the xe2x80x9ccarryxe2x80x9d passes through several stages, returning them all to the xe2x80x9czeroxe2x80x9d state. Were the flip-flops of the counter not clocked externally, the process of changing several flip-flops might cause the counter for a short interval to assume one or more intermediate states outside the proper binary sequence.
Indeed, some simple finite state machines, including binary counters are often built without an external clock for their flip-flops. In such counters, called xe2x80x9cripple counters,xe2x80x9d the state flip-flops that hold the count each act independently. The flip-flop holding each bit of the count changes its state in response to changes from xe2x80x9conexe2x80x9d to xe2x80x9czeroxe2x80x9d in the flip-flop that holds the bit representing half its value. Thus, for example, when a six bit ripple counter changes from 001111 to 010000, it will momentarily assume the states 001110, 001100, 001000, 010000 in rapid succession even though they are out of sequence. It is well known to those familiar with ripple counters that one must exercise care in their application because such FALSE states appear in their flip-flops, albeit for very short intervals of time. For finite state machines of any complexity, the simplicity of externally-clocked flip-flops is much preferred.
One aspect of all finite state machines involves the mapping of the allowed states of the machine onto the possible states of the flip-flops that retain the state. Such a mapping is called the xe2x80x9cstate encodingxe2x80x9d used for the finite state machine because it defines the meaning of each possible state of the flip-flops. The encoding may also rule out certain combinations of flip-flop states as outside the range permitted for that finite state machine.
There are two particularly simple encodings. First, some finite state machines use a xe2x80x9cone-out-of-Nxe2x80x9d encoding in which only one state flip-flop is xe2x80x9csetxe2x80x9d for each state. This encoding rules out the state with no state flip-flops set as well as all states with more than one state flip-flop set. With the one-out-of-N encoding, each change of state sets the state flip-flop associated with the new state and clears the state flip-flop associated with the old state. The one-out-of-N state encoding, though simple, is impractical for finite state machines with large numbers of states.
A second simple state encoding is a binary state encoding. In this state encoding each state is defined by a binary combination of state flip-flops that are set and that are clear. The binary encoding permits all combinations. This encoding is suitable for some finite state machines such as the binary counter already mentioned. It has the problem, however, that some state changes may require simultaneously setting many state flip-flops and clearing many others. The need to change many state flip-flops simultaneously renders binary encoding unsuitable for some applications. Designers have learned to choose encodings suitable to the needs of each particular application.
Finite state machines use complex logic elements to control the set and clear functions of individual flip-flops. These conditions cause xe2x80x9ctransitionsxe2x80x9d in the state of the finite state machine. The collection of conditions that must be TRUE to cause a particular transition must first be combined by a logical AND function. The output of this logic function will be TRUE when all relevant conditions are TRUE. Such a function indicates an impending state transition. Next, depending on the particular encoding used, several state flip-flops may have to change for such a state transition, some being set and some being cleared. The state transition logic must deliver its output to all such state flip-flops. Finally, it is likely that several transition functions apply to some state flip-flops. Such multiple transition functions must be combined with logical OR circuits to drive the inputs of the externally-clocked state flip-flops.
In spite of the complexity of such finite state machine implementations, they are so familiar to designers today that they are widely used. Indeed there are even computer automated design methods to help designers develop the required logic from equations describing the desired behavior. The software commonly used to design finite state machines depends on the use of externally-clocked flip-flops as the medium for holding the state.
The methods currently in use for designing finite state machines evolved over a long period of time. They were developed initially for use in machines built from vacuum tubes or even earlier for machines built from relays. They have served well into the era of transistor machines, but only to the extent that the more modern technologies are used in ways similar to those of the older technologies. Thus, the use of clocked flip-flops to hold state, for example, is a form that has survived several changes in the circuit elements and circuits used to implement such flip-flops.
Now, however, most digital computing devices use complementary metal oxide semiconductor (CMOS) circuits. In current CMOS circuits the cost of wires rather than the cost of logic gates dominates area, power consumption and performance. Almost all the space in a modern CMOS circuit is occupied by interconnect wiring; the transistors forming the logic gates generally fit underneath the wires required to interconnect them. The power consumption of the circuit is dominated by the need to put electrical charge onto the wires and later to remove it. The performance of the circuits is limited largely by the time it takes to charge and discharge the wires.
Moreover, in CMOS circuits, electrical capacitance can serve a state-holding function that previously had to be done with logic elements formed into flip-flops. Indeed, the dynamic random access memory (DRAM) industry has honed to a fine level the use of capacitance to store information. In a DRAM the electrical charge stored on a tiny capacitor serves to record each bit of information. However, in other CMOS circuits, the charge on any wire can also serve to store information.
Designers use such electrical charges stored on wires in making xe2x80x9cdynamicxe2x80x9d circuits. Dynamic circuits depend for their operation on the retention of information in electrical charges on wires. Dynamic circuits are possible in CMOS because the control input of a CMOS transistor, the xe2x80x9cgatexe2x80x9d of the transistor, operates on charge rather than current. An electric charge placed on the gate of a transistor will continue to condition the behavior of the transistor for a relatively long period until the charge gradually xe2x80x9cleaksxe2x80x9d off.
The present invention uses such dynamic charge storage as the basis for a variety of finite state machines. It notes that charge placed on a CMOS conductor that connects to a number of transistor gates will condition those gates, and continue to do so for a relatively long time. Instead of storing the state of a finite state machine in a collection of state flip-flops, the present invention stores the state of a finite state machine on a set of state conductors, using the capacitive charge on those conductors to hold the state.
Unlike a state flip-flop, which is geometrically local, such a state conductor can be distributed geometrically over a wide area. It can be extended to whatever length is desired, turn corners or branch as needed, and can connect together as many components as desired. To change the state of a state flip-flop requires bringing the output of the transition logic to the state flip-flop. A state transition wire connects from the state transition logic to the state flip-flop. In contrast, to change the charge on a state conductor requires only that the state conductor be driven to the new state from anywhere along its length. The state conductor will automatically communicate the new state throughout its length.
Moreover in CMOS technology a state conductor will retain its charge state for a relatively long time. If the state must be retained indefinitely, a small xe2x80x9ckeeperxe2x80x9d can be attached to the wire. Such a keeper gently drives the wire towards its most positive state if it is already positive and gently drives it towards its most negative state if it is already negative. The keeper is sufficiently weak that it is unable to resist the intentional state changes imposed by operation of the finite state machine, but just strong enough to counteract the tiny leakage currents and the effects of electrical xe2x80x9cnoisexe2x80x9d that might otherwise disturb the charge stored on the conductor and thus improperly change its state.
Another advantage of using the charge on a state conductor to store state is the ability to use individual transistors to change its charge state. We will call such transistors xe2x80x9cdrive transistors.xe2x80x9d The two types of transistors used in CMOS circuits, N-type and P-type, drive their outputs in different directions. One or more N-type drive transistors connected anywhere along the length of a state conductor can drive it to the xe2x80x9cLOxe2x80x9d state, and likewise one or more P-type drive transistors connected anywhere along the state conductor can drive it to the xe2x80x9cHIxe2x80x9d state. Because the drains of these drive transistors each contribute capacitance to the conductor, attaching them to the conductor actually increases the ability of the conductor to store charge, thus enhancing its ability to retain state!
Moreover, if several transition conditions each must cause the state to change, several separate N-type or P-type drive transistors can be attached to the state conductor to condition it properly. The conductor goes to the LO state in response to any N-type drive transistor anywhere along its length. Likewise the conductor goes to the HI state in response to any P-type drive transistor anywhere along its length. State conductors will often accommodate more than one N-type and more than one P-type drive transistor.
It is important, however, that the N-type drive transistors and the P-type drive transistors for a single state conductor must never act simultaneously. Simultaneous drive by both types of drive transistors would represent a logical conflict, some attempting to make the state conductor HI and some attempting to make it LO. Were such conflict to occur, two bad things would happen. First, excess current would flow from the power supply to ground, consuming energy unnecessarily. Second, the charge left on the conductor might be uncertain, it not having been certain which should prevail, the N-type drive transistors, yielding the LO state, or the P-type drive transistors, yielding the HI state.
The present invention addresses this requirement to avoid conflicting drivers. Each state transition will occur when one or more N-type drive transistors connected to a particular state conductor act or one or more P-type drive transistors connected to that state conductor act. Of course, depending on the encoding chosen, several state conductors might change state at the same time, some driven by N-type drive transistors and others by P-type drive transistors, as required by the design. However, in no case will both the N-type and P-type drive transistors of a single state conductor act together.
Consider also energy consumption, another matter addressed by the present invention. In CMOS circuits a principle consumption of energy is to charge and discharge the capacitance of wires. The amount of energy consumed for an action, charging or discharging a wire, involves the capacitance of the wire which depends, of course, on its length. Thus the power consumed depends on how many charge and discharge cycles happen per unit of time and upon the length of the wires thus charged or discharged.
In a CMOS finite state machine that uses externally-clocked flip-flops there are three consumers of energy. First, the wires that carry the external clock connect to each of the state flip-flops. These clock wires charge and discharge each clock cycle, whether or not the state of the machine changes. Second, the transition wires that deliver transition commands to the flip-flops extend from the sources of the conditions to the state flip-flop. The transition wires charge and discharge in response to the transition logic. Each transition wire assumes one state before its transition can occur and returns to a neutral state after its transition, two changes per transition. Finally, the wires that report the state of the state flip-flop must extend from the state flip-flop to whatever circuits require knowledge of its state. These state flip-flop output wires change once per state transition.
In a CMOS finite state machine according to the present invention, however, the situation is quite different. First, there is no external clock, which eliminates the space and the energy consumed by the clock wires. Second, rather than localizing the state in the state flip-flops, the present invention distributes the state geometrically over the state conductors. Just as the output wires of state flip-flops extend to whatever needs knowledge of the state of the state flip-flops, the state conductor extends to wherever knowledge of the state is needed. Third, in contrast to systems using state flip-flops, the present invention extends the state conductor to the state transition logic rather than having a separate wire connecting the state transition logic to the state flip-flop. The length of wire required to extend the state conductor to the state transition logic is never longer that the transition wire would have been, and may be much shorter because it need run only from the transition logic to the nearest part of the existing state conductor. Moreover, this wire charges or discharges only once for each state transition rather than twice, thus saving energy.
Hence, instead of using two wires, one to carry transition information to the state flip-flop input and one to carry the state flip-flop output to where it is needed, the present invention uses only one wire, the state conductor, for both purposes. Drive transistors connected anywhere along the length of the state conductor change its state as needed. This reduction in complexity reduces both the total amount of wire required to implement the finite state machine and the energy consumed as it operates.
One embodiment of the present invention provides a system for asynchronously controlling state information within a circuit. This system includes a first conductor that carries a voltage that indicates a state of the circuit, as well as a first drive circuit coupled to the first conductor that is configured to drive the first conductor to a first voltage level to indicate a first state. The system also includes a second drive circuit coupled to the first conductor that is configured to drive the first conductor to a second voltage level to indicate a second state. The system additionally includes a condition input that indicates a condition. The system is configured so that the first drive circuit drives the first conductor to the first voltage level based upon the condition indicated by the condition input.
In one embodiment of the present invention, the first drive circuit is additionally configured to drive the first conductor to the first voltage level based upon the state indicated by the voltage carried on the first conductor.
In one embodiment of the present invention, the system additionally includes a keeper circuit coupled to the first conductor that is configured to hold the voltage on the first conductor at a stable value, unless the voltage is changed by the first drive circuit or the second drive circuit.
In one embodiment of the present invention, the system additionally includes a pulse generation circuit coupled to the first drive circuit, wherein the pulse generation circuit is configured to cause the first drive circuit to drive the first conductor to the first voltage level using a pulse of limited duration.
In one embodiment of the present invention, the pulse generation circuit includes a cycle of logical inversions to create the pulse. In a variation on this embodiment, the cycle of logical inversions provides an odd number of inversions. In another variation on this embodiment, the cycle of logical inversions provides three inversions. In yet another variation on this embodiment, the cycle of logical inversions provides five inversions.
In one embodiment of the present invention, the pulse generation circuit includes a circuit that implements an AND function.
In one embodiment of the present invention, the voltage on the first conductor can be changed by driving the first conductor at any point along a length of the first conductor.
In one embodiment of the present invention, the system includes additional drive circuits coupled to the first conductor.
In one embodiment of the present invention, the system includes additional condition inputs that are configured to influence the first drive circuit.
In one embodiment of the present invention, the first drive circuit includes one of, a P-type transistor and an N-type transistor.
In one embodiment of the present invention, the first drive circuit includes a series stack of drive transistors.
One embodiment of the present invention provides a system for controlling asynchronous data transfers within a circuit. This system operates by monitoring a first voltage level on a first conductor that specifies whether a first stage of the circuit contains data. The system also monitors a second voltage level on a second conductor that specifies whether a second stage of the circuit contains data. Upon detecting that the first voltage level indicates that first stage contains data to be transmitted to the second stage, and that the second voltage level indicates that the second stage does not contain data, and is therefore available to receive data from the first stage, the system transfers the data from the first stage to the second stage. This is accomplished by generating a second stage latch signal to latch data into the second stage from the first stage. It also involves changing the first voltage level to indicate that the first stage no longer contains data, and changing the second voltage level to indicate that the second stage contains data.
In a variation on the above embodiment, the system additionally monitors a third voltage level on a third conductor that specifies whether a third stage of the circuit contains data. Upon detecting that the second voltage level indicates that second stage contains data to be transmitted to the third stage, and that the third voltage level indicates that the third stage does not contain data, and is therefore available to receive data from the second stage, the system transfers the data from the second stage to the third stage.